package codingforgreat.class39;


// 来自腾讯
// 给定一个只由0和1组成的字符串S，假设下标从1开始，规定i位置的字符价值V[i]计算方式如下 :
// 1) i == 1时，V[i] = 1
// 2) i > 1时，如果S[i] != S[i-1]，V[i] = 1
// 3) i > 1时，如果S[i] == S[i-1]，V[i] = V[i-1] + 1
// 你可以随意删除S中的字符，返回整个S的最大价值
// 字符串长度<=5000
public class Class01_AddValue {
    public int max1(String s) {
        char[] str = s.toCharArray();
        int[] arr = new int[str.length];
        for(int i = 0;i < arr.length;i++){
            arr[i] = str[i] == '0' ? 0 : 1;
        }
        return process(arr,0,0,0);
    }
    public int process(int[] arr,int index,int pre,int curValue){
        if(index == arr.length){
            return 0;
        }
        int bestValue = arr[index] == pre ? curValue + 1 : 1;
        //保留
        int p1 = process(arr,index + 1,arr[index],bestValue);
        int p2 = process(arr,index + 1,pre,curValue);
        return Math.max(p1 + bestValue,p2);
    }
}
